package 面试题34_二叉树中和为某一值的路径;

import org.junit.Test;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 12:26 2021/3/14
 * @Description：
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    List<List<Integer>> result = new LinkedList<>();
    Stack<Integer> pathStack = new Stack<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {

        if (root == null) return result;

        int currentSum = 0;

        findPath(root, target, currentSum);

        return result;
    }

    void findPath(TreeNode pNode, int target, int currentSum) {

        // 处理当前节点
        currentSum += pNode.val;
        pathStack.add(pNode.val);

        // 到达叶子节点后，才算一条路径
        if (currentSum == target && pNode.left == null && pNode.right == null) {
            List<Integer> path1 = new LinkedList<>();
            for (int i : pathStack) {
                path1.add(i);
            }

            result.add(path1);
        }

        // 处理左右子树
        if (pNode.left != null) {
            findPath(pNode.left, target, currentSum);
        }
        if (pNode.right != null) {
            findPath(pNode.right, target, currentSum);
        }

        // 达到叶子节点后，开始返回
        pathStack.pop();
    }

    @Test
    public void test() {
        TreeNode node1 = new TreeNode(7);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(5);
        TreeNode node4 = new TreeNode(1);
        TreeNode node5 = new TreeNode(11);
        TreeNode node6 = new TreeNode(13);
        TreeNode node7 = new TreeNode(4);
        TreeNode node8 = new TreeNode(4);
        TreeNode node9 = new TreeNode(8);
        TreeNode node10 = new TreeNode(5);

        node5.left = node1;
        node5.right = node2;

        node6.left = node3;
        node6.right = node4;

        node7.left = node5;

        node9.left = node6;
        node9.right = node8;

        node10.left = node7;
        node10.right = node9;

        pathSum(node10, 22);
    }
}
